Fast Fourier Transform (FFT) and inverse transform (IFFT) algorithms are frequently used in Digital Signal Processing and multimedia applications such as digital audio encoding and decoding. Implementation of FFT/IFFT algorithms can be performed on large mainframe computers or on smaller personal computers. Once the FFT/IFFT algorithm is completed, the data array produced by the algorithm is either in a bit reverse order or a natural order. Typically, the input data is in natural order, so the output will be in bit-reverse order. However, it is desirable that the data be converted to natural order for subsequent processes.
In a conventional scalar processing system, this conversion is completed by using a look-up table. A look-up table is a translation table that translates the bit reverse order-data array into a natural order-data array by “looking up” the index-mapping information in a table. FIG. 1 is a flowchart of the operation of a conventional scalar processing system. First, an FFT/IFFT algorithm generates a data array in bit reverse order, via step 10. Next, look up tables are utilized to convert the set of data from bit reverse order to natural order, via step 12. This is an extremely time consuming process however, because every item of data in the data array must be addressed and accessed separately and individually by the scalar processing system.
To better understand the conventional methodology, please refer to FIG. 2. FIG. 2 is a data array 20 with N=2M items populated in it. In this example, N=16. Please observe the relationship between column 3 (index in binary) and column 4 (bit-reverse index in binary) wherein if an item from column 3 is read from right to left, it is identical to the item in column 4. That is, column 4 is the bit-reverse index of column 3.
Please refer now to FIG. 3. FIG. 3 is a look-up table comprising columns 1, 2, and 5 of the data array 20 of FIG. 2. In order to subsequently convert the data items (column 1) from bit-reverse order (column 5) to natural order (column 2), each data item in the data array 20 is addressed and accessed separately by the scalar processing system. FIG. 3(a) illustrates the required steps of the conventional conversion method. For example, in step 0, element 0(0) of column 2 is matched with element 0(0) of column 5. Accordingly, element 0(0) of column 5 is located at Line 0 and the corresponding data item (95) is recorded; in step 1, element 1(1) of column 2 is matched with element 1(1) of column 5. Here, element 1(1) of column 5 is located at Line 8 and the corresponding data item (82) is recorded; etc. Thus, the natural order 95, 82, 89, 92, 60, 61, 45, 17, 23, 44, 76, 73, 48, 79, 1, 40 is established. However, because each data item in the data array is addressed and accessed separately by the scalar processing system, this is a very time consuming process. Furthermore, this conventional process requires excess utilization of scratch memory.
Accordingly, what is needed is a more efficient way of converting a data array from bit reverse order to natural order. The present invention addresses such a need.